The present invention relates to implementations of transactional memory. More specifically, the present invention relates to validating transactional operations in accordance with a global indication of read-write conflicts in a transactional memory space while supporting semi-transparent shared reading of the transactional memory space.
Current multi-processor architectures do not support synchronization primitives that can atomically access multiple memory locations. However, software transactional memory implementations have been proposed to provide atomic access to multiple memory locations in a multiple processor environment. Transactional memory may be implemented with software transactional memory or a hybrid of hardware and software transactional memory. Regardless of whether the transactional memory is implemented with software transactional memory or software transactional memory that uses hardware transactional memory support, current implementations do not allow concurrent transactions to read common memory locations without causing each other to abort if one of the transactions modifies one of the common memory locations.
Most software transactional memory algorithms utilize an ownership mechanism, which guarantees that a transaction “owns” a memory location in order to safely update it without conflicting with other transactions. While multiple transactions are typically prevented from accessing a memory location for write purposes to avoid corruption of data, multiple transactions are typically permitted to simultaneously read from the same location without aborting each other. Allowing multiple transactions to read a same location without aborting each other is referred to as read sharing. In addition to supporting read sharing, implementations should guarantee the atomicity of a transaction. Before a transaction can commit, it must determine that no other transaction has modified a location that it accesses; this is called “validation.” In many cases, it is necessary to repeatedly validate a transactional read during execution of a transaction to avoid incorrect behavior as a result of observing inconsistent data.
There are two techniques typically employed that enable read sharing in current software transactional memory algorithms: 1) transparent reading and 2) non-transparent reading. These techniques typically employ structures, referred to as ownership records, to indicate ownership of memory locations represented with the ownership record. With “transparent reading,” a transaction does not acquire ownership on a location before reading it but instead records identifiers of the ownership records that represent locations read by the transaction. In software transactional memory, implementations that use transparent reading (also known as “invisible reading”), a transaction which modifies a memory location is not aware of the currently executing transactions that have read or are reading this location. For a transaction to verify that previously read locations have not changed during execution of the transaction (i.e., validate the reading of the locations), the transaction rereads the ownership records. If the transaction has read locations represented by numerous ownership records, then the validation procedure of rereading all of the ownership records will be expensive. The validation procedure is utilized to avoid incorrect behavior like infinite loops and divide by zero, due to inconsistent read values.
With “non-transparent reading” (also known as “visible reading”), transactions that read locations do not iterate over the locations or representative ownership records to validate their read accesses. Instead, a transaction that modifies a location can determine the identity of each concurrent transaction that has read the location (e.g., with a linked list of references for the reader transactions) and explicitly aborts each of those transactions. Aborting all of the reader transactions is significantly expensive. In addition, maintaining and managing the list of reader transactions introduces complexity and is often expensive.